/*
提交链接:https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
17. 电话号码的字母组合
赖德檀 2024/12/28
*/

class Solution {
public:
    vector<string> arr;
    void dfs(unordered_map<int,string>& mp,string &digits,int n,int t,string &s1)
    {
        if(n==t)
        {
            arr.push_back(s1);
           return ; 
        }
        int k=digits[t]-'0';
        string s=mp[k];
        for(int i=0;i<s.size();i++)
        {
            s1+=s[i];
            dfs(mp,digits,n,t+1,s1);
            s1.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        int n=digits.size();
        if(digits.size()==0)
        return arr;
        unordered_map<int,string>mp;
        mp[2]="abc";
        mp[3]="def";
        mp[4]="ghi";
        mp[5]="jkl";
        mp[6]="mno";
        mp[7]="pqrs";
        mp[8]="tuv";
        mp[9]="wxyz";
        if(digits.size()==1)
        {
            char x=digits[0];
            string s=mp[x-'0'];
            for(int j=0;j<s.size();j++)
            {
                string t;
                t+=s[j];
                arr.push_back(t);
            }
        return arr;
        }
        string s1;
        dfs(mp,digits,n,0,s1);
        return arr;
    }
};